1. Field of the Invention
The present invention relates to large scale memories and, more particularly, to a memory system which automatically provides "good" memory location in response to any permitted address and a method therefor.
2. Description of the Prior Art
The creation of very large, addressable memories, often resulted, as an expected outcome of the production process, in defective regions which could not be used for the storage of information. Generally, with fairly large memories, it is either not possible or quite expensive and time consuming to attempt to repair such defects; and accordingly, to avoid the need for expensive repairs or for discarding a substantially "good" memory because of a few "bad" locations, various schemes have been proposed to correct the problem.
In order to utilize memories in which defects are randomly located throughout the memory, several approaches have been proposed. One such approach has required the use of a content addressable memory in which is stored all of the addresses which, upon an initial examination, have proven to be defective or "bad". A second, smaller memory is used to store "good" addresses which can then be substituted for the defective or "bad" ones.
In order to use such a scheme, a proposed address would be applied to the content addressable memory, which would then compare its contents to the applied address. If the address was not found within the memory, the address could be used to access the corresponding location in the main memory. If, however, a match were found, then the second memory would provide the substitute address which would be used to access a "good" location in the main memory.
The problem with a content addressable memory is its fairly slow speed and the large number of time-consuming sequential binary comparison steps that must be taken by it before presence or absence of a bad memory location is verified by it and a memory location is actually made available for the storage or retrieval of information.
Another approach has been a "hard-wired" approach in which an address, when applied to the memory, does not access the location normally represented by that address, but rather, the resulting energizing signals are applied to a substitute or different location, which is known to be good. This process required access to the addressing circuits and the reconnection of the address outputs to the new, otherwise unused locations.
In this approach, no time is lost during operation of the memory, although substantial time and expense is entailed in the rewiring process. Further, while a core memory may be rewired, although with difficulty, a semi-conductor memory presents special problems that make "hard-wiring" a less desirable alternative.
What is required is a simple, easily fabricated, large scale memory with an ancillary store that will supply substitute good locations for applied "bad" locations with a minimal delay in the actual access of the memory.
In creating a memory which can appear to the user as a perfect, defect-free memory, an analysis has been undertaken to determine, on a statistical basis, the probability of failures occurring in a memory of given size. For example, in one particular type of memory which was analyzed the probability of having one defective location in a thousand word memory is fairly high. However, the probability that there would be two defective locations is much lower and the probability of three defective locations occurring is quite small. The statistics will vary for different memories, but are believed to be generally similar for present day memories, such as core and semiconductor memories.
The probability of four defective locations existing in a thousand "word" block is generally so small, that it can be ignored for all practical purposes. Accordingly, a scheme that need accommodate no more than three defects per thousand words should lead to the acceptance of enough otherwise rejected memories such that the occasional memory with four defects per thousand words can be repaired or discarded without materially impacting overall production costs.
A memory built according to this concept would then only need an extra three addressable words per thousand words to accommodate all of the failures that could normally be expected to occur on a random, statistical basis. In a million word memory, this suggests that the provision or designation of three thousand "spare" words which are available for substitute addressing should dramatically increase the acceptable product yield. These spares can either be located in a concentrated area of the memory such as in three, thousand word increments or blocks, or can be distributed throughout the memory.
Further, and still dealing with the example of the million word memory, if the memory is subdivided into a thousand blocks of a thousand words each, then each word can be uniquely identified by a combination of twenty binary digits. Ten digits can specify the "block" and ten digits specify the word within the block.
Generally addressable memories are organized in gross or large increments such as the above described "blocks" and are subdivided within each gross increment or block into fine or small increments such as the above described "words". Each address then includes a gross portion or block address that identifies the larger increment and a fine portion or word address that identifies a small increment within the identified large increment.
In accordance with an underlying concept of the present invention, the gross or block address portion of an address simultaneously identifies a gross increment of the main memory and a corresponding fine increment of an auxiliary memory, which may, of course, be a special one of the gross increments of the main memory.
Further, the auxiliary memory can be subdivided into a first address file and a second address file. A gross or block address portion of an address then identifies a fine increment or word in each of the address files. Stored in the auxiliary memory in the first address file are the addresses of all fine increments of the main memory which contain defects or errors and, in the second address file, the addresses of substitute, fine increments of the main memory are stored, organized as described above.
In one preferred million word embodiment of the invention, an auxiliary memory is provided with the same number of "words" as there are accessible "blocks" in the memory with which it is associated. Each auxiliary memory word is capable of storing up to three addresses of defective locations within the block, which is the statistical expectation. Associated with each of the "defective" addresses, in the same "word", can be stored three substitute addresses, each corresponding to one of the defective addresses.
If the spare or substitute locations are in the same block as the defective words, each defective location address and corresponding substitute location address can comprise a 10 bit word segment. The corresponding defective and substitute addresses can be grouped together in 20 bit word segments, or all of the defective addresses can form one part of the word while the substitute addresses can be grouped together to form a second part of the word. Other memory schemes could be devised in which the substitute locations require either more or less bits to specify the address.
In a preferred embodiment, an additional pair of bits is stored in conjunction with the defective addresses to specify how many defective addresses are actually stored in the word. Obviously, if only one defective address is encountered in a block, then only the contents of that portion of the word representing the one defective address is of interest and the remaining bits, normally allocated to other defective addresses, can be ignored.
A plurality of comparators, in our example, three, are provided to simultaneously compare an applied address to the stored defective addresses of the word associated with the address block. The stored, defective addresses then are simultaneously compared with the applied address for a match. If a match is found, the part of the word containing the address of the corresponding, substitute location can be read out and applied to the addressing circuits so that the substitute, good location in the main memory can be accessed. Through the use of the extra bits, which signal the number of stored defective addresses that are present, only the appropriate number of comparators is energized and the remaining parts of the word, in which no addresses are stored, need not be considered.
In various embodiments, the auxiliary or address memory can either be a single memory or may be two, smaller memory units, one for the storage of defective address locations and the other for the storage of the substitute address locations.
The address files may be programmable, read-only memories (PROM) with a plurality of words, each corresponding to a different block of the main memory. The second address file may be similar PROM or may be a part of the same PROM. Each PROM word of the second file can correspond to a PROM word in the first file to store a replacement address to correspond to each stored address which designates a "bad" location.
If the alternative or spare locations are not distributed at random throughout the memory but are located either in the same block as the defective address location or in predetermined, otherwise unused blocks of the memory, then the addresses stored in the second file need not include the entire address of the alternative location. If each block includes "spare addresses", the block portion of the address neet not be repeated. Similarly, if entire blocks are set aside for alternative locations, each comparator can be assigned to a block and the block address can be generated separately by a permanent, address generator. The PROM memory then need only store the bits specifying a particular location within that block.
In operation, when any applied address corresponds to a "bad" storage location, a substitute address is generated in its place, and is applied to the memory, without the user being aware of the substitution. No special modification of the memory is needed, other than the provision of sufficient "spare" locations within the memory.
According to the present invention, the address files, in which the defective address locations and substitute address locations are stored, can be created upon the initial testing of the main memory. In a first embodiment, a pair of programmable, read only memories (PROMS) are provided to store addresses that are to be used in conjunction with the memory.
Initially, the main memory is tested, location by location, with test apparatus capable of signalling errors or defects. These signals can be used to cause an address to be written in the first address file. A counter may keep track of the defects as they are found.
At the conclusion of the test of an individual block, the addresses in which the defects have been found are recorded in the PROM, and the counter output, representing the number of defects found, is also written into the PROM word. In general, if more than three defects are noted in a thousand word block, the counter can signal that the block is "defective" and may require "rework" or rejection.
When the entire memory had been tested and all of the defective locations identified, the addresses of locations in the main memory designated as "spares" which are not normally utilized are then loaded into the second address file. Thus, each defective location address in the first file, has a counterpart or "spare" or substitute address stored in the second file.
When the memory testing cycle is completed, the two address files will have been created. In subsequent use and operation of the memory, all addresses may be accepted. However, only those which correspond to "good" locations are actually used to access the location. Those addresses which represent defective or "bad" locations are recognized, and substitute addresses are applied to the memory, thereby furnishing a substitute "good" location without any additional time being required.
The novel features which are believed to be characteristic of the invention, both as to organization and method of operation, together with further objects and advantages thereof will be better understood from the following description considered in connection with the accompanying drawings in which several preferred embodiments of the invention are illustrated by way of example. It is to be expressly understood, however, that the drawings are for the purpose of illustration and description only and are not intended as a definition of the limits of the invention.